package DynamicProgram.completeBag;

/**
 * @ClassName ChangeII
 * @Description TODO
 * @Author lenovo
 * @Date 2023-08-21 9:46
 * @Version 1.0
 * @Comment Magic. Do not touch.
 * If this comment is removed. the program will blow up
 */
public class ChangeII {
    /**
     * 给定不同面额的硬币和一个总金额。写出函数来计算可以凑成总金额的硬币组合数。假设每一种面额的硬币有无限个。
     * <p>
     * 示例 1:
     * <p>
     * 输入: amount = 5, coins = [1, 2, 5]
     * 输出: 4
     * 解释: 有四种方式可以凑成总金额:
     * <p>
     * 5=5
     * 5=2+2+1
     * 5=2+1+1+1
     * 5=1+1+1+1+1
     * 示例 2:
     * <p>
     * 输入: amount = 3, coins = [2]
     * 输出: 0
     * 解释: 只用面额2的硬币不能凑成总金额3。
     * 示例 3:
     * <p>
     * 输入: amount = 10, coins = [10]
     * 输出: 1
     * 注意，你可以假设：
     * <p>
     * 0 <= amount (总金额) <= 5000
     * 1 <= coin (硬币面额) <= 5000
     * 硬币种类不超过 500 种
     * 结果符合 32 位符号整数
     */

    public int change(int amount, int[] coins) {
        int[] dp = new int[amount + 1];
        //初始化dp数组，表示金额为0时只有一种情况，也就是什么都不装
        dp[0] = 1;
        for (int i = 0; i < coins.length; i++) {
            for (int j = coins[i]; j <= amount; j++) {
                dp[j] = dp[j] + dp[j - coins[i]];
            }
        }
        return dp[amount];
    }

    public static void main(String[] args) {
        int amount = 3;
        int[] coins = new int[]{1, 2, 3};
//        String sql = "select * from a union all select * from b union all";
//
//        int unionAllIndex = sql.lastIndexOf("union all");
//        String substring = sql.substring(0, unionAllIndex);
//        substring += ")";
//        System.out.println(substring);
        ChangeII changeII = new ChangeII();
        System.out.println(changeII.change(amount, coins));
    }
}